#include "bitmap.h"
#include "stdlib.h"
#include "stdio.h"

BitMap::BitMap()
{
}

void BitMap::initialize(char *bitmap, const int length)
{
    this->bitmap = bitmap;
    this->length = length;

    int bytes = ceil(length, 8);

    for (int i = 0; i < bytes; ++i)
    {
        bitmap[i] = 0;
    }
}

bool BitMap::get(const int index) const
{
    int pos = index / 8;
    int offset = index % 8;

    return (bitmap[pos] & (1 << offset));
}

void BitMap::set(const int index, const bool status)
{
    int pos = index / 8;
    int offset = index % 8;

    // 清0
    bitmap[pos] = bitmap[pos] & (~(1 << offset));

    // 置1
    if (status)
    {
        bitmap[pos] = bitmap[pos] | (1 << offset);
    }
}

int BitMap::allocate(const int count)
{
	return firstfit(count);
	//return bestfit(count);
	//return next(count);
}

int BitMap::firstfit(const int count)
{
    if (count == 0)
        return -1;

    int index, empty, start;

    index = 0;
    while (index < length)
    {
        // 越过已经分配的资源
        while (index < length && get(index))
            ++index;

        // 不存在连续的count个资源
        if (index == length)
            return -1;

        // 找到1个未分配的资源
        // 检查是否存在从index开始的连续count个资源
        empty = 0;
        start = index;
        while ((index < length) && (!get(index)) && (empty < count))
        {
            ++empty;
            ++index;
        }

        // 存在连续的count个资源
        if (empty == count)
        {
            for (int i = 0; i < count; ++i)
            {
                set(start + i, true);
            }

            return start;
        }
    }
	printf("Memory allocation failed\n");
    return -1;
}


int BitMap::bestfit(const int count)
{
    if (count == 0)
        return -1;

    int index, start;
    int section[30];
    int i_s = 0;
    index = 0;
    
    //获取所有空白分区大小
    while (index < length)
    {
    	
    	while(index < length && get(index))
    		index ++;
    	int blank = 0;
    	while((index < length) && (!get(index)))
    	{
    		blank ++;
    		index ++;
    	}
    	if(blank == 0)
    	{
    		continue;
    	}
    	section[i_s] = blank;
    	i_s ++;
    }
    int num = i_s; // 空白分区总个数
    if (num == 0)
    {
    	printf("Memory allocation failed\n");
		return -1;
    }
    int target_blank = -1;
    int tmp_bestfit_blank = 0;
    //找到最小的满足需求的空白分区
    for (int i = 0; i<num;i++)
    {
    	if (i==0)
    	{
    		target_blank = 0;
    		tmp_bestfit_blank = section[0];
    		continue;
    	}
    	if(section[i]>=count && section[i]<tmp_bestfit_blank)
		{
			target_blank = i;
    		tmp_bestfit_blank = section[i];
		}
    	
    }
    target_blank ++; //注意数组下标从0开始，因此这里的目标空白区序号要加1
    //分配bestfit空白分区给作业
    index = 0;
    for(int i = 0; i< target_blank; i++)
	{
		while(index < length && get(index))
			index++;
		if(i == target_blank-1)
		{
			start = index;
			for (int j = 0; j < count; ++j)
            {
                set(start + j, true);
            }

            return start;
		}
		
		while(index < length && !get(index))
			index++;
	}
	printf("Memory allocation failed\n");
	return -1;
}

void BitMap::release(const int index, const int count)
{
    for (int i = 0; i < count; ++i)
    {
        set(index + i, false);
    }
}

char *BitMap::getBitmap()
{
    return (char *)bitmap;
}

int BitMap::size() const
{
    return length;
}
